package 排序;

/**
 * @author ssh
 * @date 2025/11/26
 * @description 堆排序
 */
public class 堆排序 {

    public void sort(int[] arr) {
        int n = arr.length;

        // 构建堆（重新排列数组）
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }

        // 一个个从堆中提取元素
        for (int i = n - 1; i > 0; i--) {
            // 将当前根移动到末尾
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            // 对缩小的堆调用最大堆化
            heapify(arr, i, 0);
        }
    }

    // 堆化一个以节点 i 为根的子树，i 是 arr[] 中的一个索引。n 是堆的大小
    void heapify(int[] arr, int n, int i) {
        // 将最大值初始化为根
        int largest = i;
        // 左子节点 = 2*i + 1
        int l = 2 * i + 1;
        // 右子节点 = 2*i + 2
        int r = 2 * i + 2;

        // 如果左子节点大于根
        if (l < n && arr[l] > arr[largest]) {
            largest = l;
        }

        // 如果右子节点大于目前的最大值
        if (r < n && arr[r] > arr[largest]) {
            largest = r;
        }

        // 如果最大值不是根
        if (largest != i) {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;

            // 递归地堆化受影响的子树
            heapify(arr, n, largest);
        }
    }

    /* 一个打印大小为 n 的数组的工具函数 */
    static void printArray(int[] arr) {
        int n = arr.length;
        for (int j : arr) {
            System.out.print(j + " ");
        }
        System.out.println();
    }

    // 主程序
    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6, 7};

        堆排序 ob = new 堆排序();
        ob.sort(arr);

        System.out.println("排序后的数组是");
        printArray(arr);
    }
}

